{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wordPattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词规律"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一种规律 <code>pattern</code>&nbsp;和一个字符串&nbsp;<code>s</code>&nbsp;，判断 <code>s</code>&nbsp;是否遵循相同的规律。</p>\n",
    "\n",
    "<p>这里的&nbsp;<strong>遵循&nbsp;</strong>指完全匹配，例如，&nbsp;<code>pattern</code>&nbsp;里的每个字母和字符串&nbsp;<code>s</code><strong>&nbsp;</strong>中的每个非空单词之间存在着双向连接的对应规律。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> pattern = <code>\"abba\"</code>, s = <code>\"dog cat cat dog\"</code>\n",
    "<strong>输出:</strong> true</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>pattern = <code>\"abba\"</code>, s = <code>\"dog cat cat fish\"</code>\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> pattern = <code>\"aaaa\"</code>, s = <code>\"dog cat cat dog\"</code>\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pattern.length &lt;= 300</code></li>\n",
    "\t<li><code>pattern</code>&nbsp;只包含小写英文字母</li>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 3000</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母和&nbsp;<code>' '</code></li>\n",
    "\t<li><code>s</code>&nbsp;<strong>不包含</strong> 任何前导或尾随对空格</li>\n",
    "\t<li><code>s</code>&nbsp;中每个单词都被 <strong>单个空格 </strong>分隔</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-pattern](https://leetcode.cn/problems/word-pattern/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-pattern](https://leetcode.cn/problems/word-pattern/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abba\"\\n\"dog cat cat dog\"', '\"abba\"\\n\"dog cat cat fish\"', '\"aaaa\"\\n\"dog cat cat dog\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        p_s_dict = {}\n",
    "        s_p_dict = {}\n",
    "\n",
    "        flag = False\n",
    "        pattern_idx = 0\n",
    "\n",
    "        def bt(i):\n",
    "            nonlocal flag, pattern_idx\n",
    "            if flag:\n",
    "                return\n",
    "            elif i == len(s) and pattern_idx == len(pattern):\n",
    "                flag = True\n",
    "                return\n",
    "            elif i == len(s) or pattern_idx == len(pattern):\n",
    "                return\n",
    "                \n",
    "            for next_idx in range(i + 1, len(s) + 1):\n",
    "                s_add, p_add = False, False\n",
    "                s_part = s[i: next_idx]\n",
    "                p_part = pattern[pattern_idx]\n",
    "                if s_part not in s_p_dict:\n",
    "                    s_add = True\n",
    "                    s_p_dict[s_part] = p_part\n",
    "                else:\n",
    "                    if s_p_dict[s_part] != p_part:\n",
    "                        continue\n",
    "\n",
    "                if p_part not in p_s_dict:\n",
    "                    p_add = True\n",
    "                    p_s_dict[p_part] = s_part\n",
    "                else:\n",
    "                    if p_s_dict[p_part] != s_part:\n",
    "                        s_add = False\n",
    "                        s_p_dict.pop(s_part)\n",
    "                        continue\n",
    "                pattern_idx += 1\n",
    "                bt(next_idx)\n",
    "                pattern_idx -= 1\n",
    "                if s_add:\n",
    "                    s_p_dict.pop(s_part)\n",
    "                if p_add:\n",
    "                    p_s_dict.pop(p_part)\n",
    "                \n",
    "        \n",
    "        bt(0)\n",
    "        return flag\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        word_dict = {}\n",
    "        success = False\n",
    "        pattern_len, s_len = len(pattern), len(s)\n",
    "\n",
    "        def dfs(pattern_begin, s_begin):\n",
    "            nonlocal success\n",
    "            if pattern_begin == pattern_len and s_begin == s_len:\n",
    "                success = True\n",
    "                return\n",
    "            for i in range(pattern_begin, pattern_len):\n",
    "                key = pattern[i]\n",
    "                for j in range(s_begin, s_len):\n",
    "                    value = s[s_begin:j+1]\n",
    "                    if key not in word_dict:\n",
    "                        if value not in word_dict.values():\n",
    "                            word_dict[key] = value\n",
    "                            dfs(i+1, j+1)\n",
    "                            del word_dict[key]\n",
    "                        else:\n",
    "                            continue\n",
    "                    elif value == word_dict[key]:\n",
    "                        dfs(i+1, j+1)\n",
    "                    if success:\n",
    "                        return\n",
    "                if not success:\n",
    "                    break\n",
    "        dfs(0, 0)\n",
    "        return success\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        self.pre=dict()\n",
    "        self.next=dict()\n",
    "        def dfs(lists1,lists2):\n",
    "            if not lists1 and not lists2:\n",
    "                return True\n",
    "            if not lists1:\n",
    "                return False\n",
    "            elif not lists2:\n",
    "                return False\n",
    "            else:\n",
    "                if lists1[0] in self.pre.keys():\n",
    "                    if len(lists2)<len(self.pre[lists1[0]]) or lists2[:len(self.pre[lists1[0]])]!=self.pre[lists1[0]]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        return dfs(lists1[1:], lists2[len(self.pre[lists1[0]]):])\n",
    "                else:\n",
    "                    for i in range(len(lists2)):\n",
    "                        if lists2[:i+1] not in self.next.keys():\n",
    "                            self.pre[lists1[0]]=lists2[:i+1]\n",
    "                            self.next[lists2[:i+1]]=lists1[0]\n",
    "                            if dfs(lists1[1:], lists2[i+1:]):\n",
    "                                return True\n",
    "                            del self.pre[lists1[0]]\n",
    "                            del self.next[lists2[:i+1]]\n",
    "                    return False\n",
    "        return dfs(pattern,s)\n",
    "                            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        hashmap={}\n",
    "        def dfs(pattern,pindex,s,sindex):\n",
    "            if pindex ==len(pattern):\n",
    "                return sindex==len(s)\n",
    "            curPattern = pattern[pindex]\n",
    "            if curPattern in hashmap:\n",
    "                mathword = hashmap[curPattern]\n",
    "                if s[sindex:sindex+len(mathword)]!=mathword:\n",
    "                    return False \n",
    "                return dfs(pattern,pindex+1,s,sindex+len(mathword))\n",
    "            res = False \n",
    "            for endindex in range(sindex+1,len(s)+1):\n",
    "                possibleworld = s[sindex:endindex]\n",
    "                if possibleworld in hashmap.values():\n",
    "                    continue \n",
    "                hashmap[curPattern] = possibleworld\n",
    "                res = res or dfs(pattern,pindex+1,s,sindex+len(possibleworld))\n",
    "                del hashmap[curPattern]\n",
    "            return res \n",
    "        return dfs(pattern,0,s,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "\n",
    "        def is_ok(p, word, prev_map):\n",
    "            if len(p) == 1:\n",
    "                if p in prev_map:\n",
    "                    if prev_map[p] == word:\n",
    "                        return True\n",
    "                    return False\n",
    "                else:\n",
    "                    if word in prev_map.values():\n",
    "                        return False\n",
    "                    return True\n",
    "            else:\n",
    "                for i in range(1, len(word)):\n",
    "                    sub1 = word[:i]\n",
    "                    if p[0] in prev_map:\n",
    "                        if prev_map[p[0]] == sub1:\n",
    "                            ans1 = is_ok(p[1:], word[i:], prev_map)\n",
    "                            if ans1:\n",
    "                                return True\n",
    "                    else:\n",
    "                        if sub1 not in prev_map.values():\n",
    "                            pp1 = prev_map.copy()\n",
    "                            pp1[p[0]] = sub1\n",
    "                            ans1 = is_ok(p[1:], word[i:], pp1)\n",
    "                            if ans1:\n",
    "                                return True\n",
    "                return False\n",
    "\n",
    "        ret = is_ok(pattern, s, {})\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.wordPatternMatch(pattern = \"abab\", s = \"redblueredblue\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "\n",
    "        def matching(i: int, j: int, words: dict, vals: set) -> bool:\n",
    "\n",
    "            if j == len(pattern):\n",
    "                return i == len(s)\n",
    "            w = pattern[j]\n",
    "            if w in words:\n",
    "                word = words[w]\n",
    "                if i + len(word) > len(s):\n",
    "                    return False\n",
    "                p_s = s[i: i + len(word)]\n",
    "                if word != p_s:\n",
    "                    return False\n",
    "\n",
    "                return matching(i + len(word), j + 1, words, vals)\n",
    "            else:\n",
    "                ress = False\n",
    "                for k in range(i, len(s)):\n",
    "                    ss = s[i: k + 1]\n",
    "                    if ss not in vals:\n",
    "                        words[w] = ss\n",
    "                        vals.add(ss)\n",
    "                        ress |= matching(k + 1, j + 1, words, vals)\n",
    "                        vals.remove(ss)\n",
    "                        del words[w]\n",
    "\n",
    "                return ress\n",
    "\n",
    "        return matching(0, 0, dict(), set())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        v = set()\n",
    "        dict_ = dict()\n",
    "        \n",
    "        def dfs(pattern, s):\n",
    "            if len(pattern) == 0:\n",
    "                return len(s) == 0\n",
    "            else:\n",
    "                ch = pattern[0]\n",
    "                if ch in dict_:\n",
    "                    if s.startswith(dict_[ch]):\n",
    "                        return dfs(pattern[1:], s[len(dict_[ch]):])\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    for length in range(1, len(s) + 1):\n",
    "                        if s[:length] not in v:\n",
    "                            word = s[:length]\n",
    "                            v.add(word)\n",
    "                            dict_[ch] = word\n",
    "                            if dfs(pattern[1:], s[len(word):]):\n",
    "                                return True \n",
    "                            del dict_[ch]\n",
    "                            v.remove(word)\n",
    "                    return False\n",
    "        \n",
    "        return dfs(pattern, s)\n",
    "\n",
    "                         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 291\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        if not pattern or not s:                #因为题目要求的对应关系都是非空的\n",
    "            return False\n",
    "        self.char_word = defaultdict(str)\n",
    "        self.word_char = defaultdict(chr)\n",
    " \n",
    "        return self.dfs_backtrace(pattern, 0, s, 0)\n",
    " \n",
    "    def dfs_backtrace(self, pattern: str, pi: int, s: str, si: int) -> bool:\n",
    "        if pi >= len(pattern):\n",
    "            return si >= len(s)\n",
    "        if si >= len(s):\n",
    "            return False\n",
    "        c = pattern[pi]\n",
    "        if c not in self.char_word:\n",
    "            for i in range(si, len(s)):\n",
    "                word = s[si: i+1]\n",
    "                if word not in self.word_char:\n",
    "                    self.char_word[c] = word        #赋值\n",
    "                    self.word_char[word] = c        #赋值\n",
    "                    \n",
    "                    if self.dfs_backtrace(pattern, pi + 1, s, i + 1) == True:\n",
    "                        return True\n",
    "                    \n",
    "                    del self.char_word[c]        #回溯。\n",
    "                    del self.word_char[word]     #回溯。\n",
    "                else:\n",
    "                    if self.word_char[word] == c:    #满足双向映射\n",
    "                        if self.dfs_backtrace(pattern, pi + 1, s, si+len(word)):\n",
    "                            return True\n",
    "        else:\n",
    "            word = self.char_word[c]\n",
    "            if si + len(word) <= len(s):\n",
    "                tmp = s[si : si+len(word)]\n",
    "                if tmp == word:\n",
    "                    if self.dfs_backtrace(pattern, pi + 1, s, si + len(word)) == True:\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        p_s_dict = {}\n",
    "        s_p_dict = {}\n",
    "\n",
    "        flag = False\n",
    "        pattern_idx = 0\n",
    "\n",
    "        def bt(i):\n",
    "            nonlocal flag, pattern_idx\n",
    "            if flag:\n",
    "                return\n",
    "            elif i == len(s) and pattern_idx == len(pattern):\n",
    "                flag = True\n",
    "                return\n",
    "            elif i == len(s) or pattern_idx == len(pattern):\n",
    "                return\n",
    "                \n",
    "            for next_idx in range(i + 1, len(s) + 1):\n",
    "                s_add = False\n",
    "                p_add = False\n",
    "                s_part = s[i: next_idx]\n",
    "                p_part = pattern[pattern_idx]\n",
    "                if s_part not in s_p_dict:\n",
    "                    s_add = True\n",
    "                    s_p_dict[s_part] = p_part\n",
    "                else:\n",
    "                    if s_p_dict[s_part] != p_part:\n",
    "                        continue\n",
    "\n",
    "                if p_part not in p_s_dict:\n",
    "                    p_add = True\n",
    "                    p_s_dict[p_part] = s_part\n",
    "                else:\n",
    "                    if p_s_dict[p_part] != s_part:\n",
    "                        s_p_dict.pop(s_part)\n",
    "                        s_add = False\n",
    "                        continue\n",
    "                pattern_idx += 1\n",
    "                bt(next_idx)\n",
    "                pattern_idx -= 1\n",
    "                if s_add:\n",
    "                    s_p_dict.pop(s_part)\n",
    "                if p_add:\n",
    "                    p_s_dict.pop(p_part)\n",
    "                \n",
    "        \n",
    "        bt(0)\n",
    "        return flag\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        s_len = len(s)\n",
    "        p_len = len(pattern)\n",
    "\n",
    "        def backtracking(s_idx, p_idx, word_map, word_set):\n",
    "            if  p_idx == p_len:\n",
    "                return s_idx == s_len\n",
    "\n",
    "            p = pattern[p_idx]\n",
    "            if p in word_map:\n",
    "                w = word_map[p]\n",
    "                if not s[s_idx:s_idx+len(w)] == w:\n",
    "                    return False\n",
    "                return backtracking(s_idx + len(w), p_idx + 1, word_map, word_set)\n",
    "            \n",
    "            for i in range(s_idx + 1, s_len + 1):\n",
    "                if s[s_idx:i] in word_set:\n",
    "                    continue\n",
    "                word_map[p] = s[s_idx:i]\n",
    "                word_set.add(s[s_idx:i])\n",
    "                if backtracking(i, p_idx + 1, word_map, word_set):\n",
    "                    return True\n",
    "                word_map.pop(p)\n",
    "                word_set.remove(s[s_idx:i])\n",
    "            return False\n",
    "\n",
    "        return backtracking(0, 0, {}, set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        n, m = len(pattern), len(s)\n",
    "        def dfs(i1, i2, d):\n",
    "            if i1 == n:\n",
    "                return i2 == m\n",
    "            if i2 == m:\n",
    "                return i1 == n\n",
    "            cur = pattern[i1]\n",
    "            if cur in d:\n",
    "                pair = d[cur]\n",
    "                # for nex in range(i2, m):\n",
    "                if s[i2:i2+len(pair)] == pair and dfs(i1+1, i2+len(pair), d):\n",
    "                    return True\n",
    "            else:\n",
    "                has = set(d.values())\n",
    "                for nex in range(i2, m):\n",
    "                    if s[i2:nex+1] not in has:\n",
    "                        d[cur] = s[i2:nex+1]\n",
    "                        if dfs(i1+1, nex+1, d):\n",
    "                            return True\n",
    "                        del d[cur]\n",
    "            return False   \n",
    "        return dfs(0, 0, {})      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        hashmap = dict()\n",
    "        return self.dfs(pattern,0,s,0,hashmap)\n",
    "    \n",
    "    def dfs(self, pattern, pindex, s, sindex, hashmap):\n",
    "        if pindex == len(pattern):\n",
    "            return sindex == len(s)\n",
    "\n",
    "        curp = pattern[pindex]\n",
    "\n",
    "        if curp in hashmap:\n",
    "            matchword = hashmap[curp]\n",
    "            if s[sindex: sindex+len(matchword)] != matchword:\n",
    "                return False\n",
    "            return self.dfs(pattern, pindex+1, s, sindex+len(matchword), hashmap)\n",
    "\n",
    "        res = False\n",
    "\n",
    "        for end in range(sindex+1, len(s)+1):\n",
    "            possible = s[sindex: end]\n",
    "            if possible in hashmap.values():\n",
    "                continue\n",
    "            hashmap[curp] = possible\n",
    "            res = res or self.dfs(pattern, pindex+1, s, sindex+len(possible), hashmap)\n",
    "            del hashmap[curp]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        hashmap=dict()\n",
    "        return self.dfs(pattern,0,s,0,hashmap)\n",
    "    \n",
    "    def dfs(self,pattern,pindex,s,sindex,hashmap):\n",
    "        if pindex==len(pattern):\n",
    "            return sindex==len(s)\n",
    "        curpattern=pattern[pindex]\n",
    "\n",
    "        if curpattern in hashmap:\n",
    "            matchword=hashmap[curpattern]\n",
    "            if s[sindex:sindex+len(matchword)]!=matchword:\n",
    "                return False\n",
    "            return self.dfs(pattern,pindex+1,s,sindex+len(matchword),hashmap)\n",
    "        res=False\n",
    "        for endindex in range(sindex+1,len(s)+1):\n",
    "            possibleword=s[sindex:endindex]\n",
    "            if possibleword in hashmap.values():\n",
    "                continue\n",
    "            hashmap[curpattern]=possibleword\n",
    "            res=res or self.dfs(pattern,pindex+1,s,sindex+len(possibleword),hashmap)\n",
    "            del hashmap[curpattern]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        res = False\n",
    "        path = []\n",
    "        n = len(s)\n",
    "\n",
    "        def valid(s):\n",
    "            if len(pattern) != len(s): return False\n",
    "            p2s, s2p = {}, {}\n",
    "\n",
    "            for i in range(len(pattern)):\n",
    "                if pattern[i] not in p2s: p2s[pattern[i]] = s[i]\n",
    "                if s[i] not in s2p: s2p[s[i]] = pattern[i]\n",
    "                if s[i] != p2s[pattern[i]] or pattern[i] != s2p[s[i]]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if res: return\n",
    "\n",
    "            if i == n:\n",
    "                if valid(path):\n",
    "                    res = True\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                sub = s[i:j+1]\n",
    "                path.append(sub)\n",
    "                dfs(j + 1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern, s) -> bool:\n",
    "        mapping = dict()\n",
    "        used = set()\n",
    "        return self.isMatch(pattern, s, mapping, used)\n",
    "\n",
    "    def isMatch(self, pattern, str, mapping, used):\n",
    "        if len(pattern) == 0:\n",
    "            return len(str) == 0\n",
    "        ch = pattern[0]\n",
    "        if ch in mapping:\n",
    "            word = mapping[ch]\n",
    "            if not str.startswith(word):\n",
    "                return False\n",
    "            return self.isMatch(pattern[1:], str[len(word):], mapping, used)\n",
    "\n",
    "        for length in range(len(str)):\n",
    "            word = str[:length+1]\n",
    "            if word in used:\n",
    "                continue\n",
    "            mapping[ch] = word\n",
    "            used.add(word)\n",
    "            if self.isMatch(pattern[1:], str[length+1:], mapping, used):\n",
    "                return True\n",
    "            used.remove(word)\n",
    "            del mapping[ch]\n",
    "        return False\n",
    "\n",
    "### 此处用的是回溯法进行匹配。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 291\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        if not pattern or not s:                #因为题目要求的对应关系都是非空的\n",
    "            return False\n",
    "        self.char_word = defaultdict(str)\n",
    "        self.word_char = defaultdict(chr)\n",
    " \n",
    "        return self.dfs_backtrace(pattern, 0, s, 0)\n",
    " \n",
    "    def dfs_backtrace(self, pattern: str, pi: int, s: str, si: int) -> bool:\n",
    "        if pi >= len(pattern):\n",
    "            return si >= len(s)\n",
    "        if si >= len(s):\n",
    "            return False\n",
    "        c = pattern[pi]\n",
    "        if c not in self.char_word:\n",
    "            for i in range(si, len(s)):\n",
    "                word = s[si: i+1]\n",
    "                if word not in self.word_char:\n",
    "                    self.char_word[c] = word        #赋值\n",
    "                    self.word_char[word] = c        #赋值\n",
    "                    \n",
    "                    if self.dfs_backtrace(pattern, pi + 1, s, i + 1) == True:\n",
    "                        return True\n",
    "                    \n",
    "                    del self.char_word[c]        #回溯。\n",
    "                    del self.word_char[word]     #回溯。\n",
    "                else:\n",
    "                    if self.word_char[word] == c:    #满足双向映射\n",
    "                        if self.dfs_backtrace(pattern, pi + 1, s, si+len(word)):\n",
    "                            return True\n",
    "        else:\n",
    "            word = self.char_word[c]\n",
    "            if si + len(word) <= len(s):\n",
    "                tmp = s[si : si+len(word)]\n",
    "                if tmp == word:\n",
    "                    if self.dfs_backtrace(pattern, pi + 1, s, si + len(word)) == True:\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        pattern_to_s=dict()\n",
    "        s_to_pattern=dict()\n",
    "        def check():\n",
    "            left,judge=0,0\n",
    "            ret=False\n",
    "            for i in pattern:\n",
    "                if ret==True:\n",
    "                    return True\n",
    "                if i in pattern_to_s:\n",
    "                    if s[left:left+len(pattern_to_s[i])]==pattern_to_s[i]:\n",
    "                        left+=len(pattern_to_s[i])\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    judge=1\n",
    "                    for j in range(left+1,len(s)+1):\n",
    "                        if s[left:j] not in s_to_pattern and i not in pattern_to_s:\n",
    "                            s_to_pattern[s[left:j]]=i\n",
    "                            pattern_to_s[i]=s[left:j]\n",
    "                            ret=ret or check()\n",
    "                            pattern_to_s.pop(i)\n",
    "                            s_to_pattern.pop(s[left:j])\n",
    "            if judge==0 and left==len(s):\n",
    "                return True\n",
    "            return ret\n",
    "        return check()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def digest(pattern: str, word: str, string: str, mapping_dict: dict):\n",
    "    if len(pattern) == 0:\n",
    "        if len(string) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    cur = pattern[0]\n",
    "    if cur == pattern[0]:\n",
    "        if string.startswith(word):\n",
    "            next_pattern = pattern[1:]\n",
    "            next_string = string[len(word):]\n",
    "            next_word = word\n",
    "            if len(pattern) == 1:\n",
    "                return digest(next_pattern, next_word, next_string, mapping_dict)\n",
    "            else:\n",
    "                next_ = pattern[1]\n",
    "                if next_ == cur:\n",
    "                    return digest(next_pattern, next_word, next_string, mapping_dict)\n",
    "                else:\n",
    "                    for i in range(1, len(next_string) + 1):\n",
    "                        generate = False\n",
    "                        if next_pattern[0] not in mapping_dict:\n",
    "                            next_word = next_string[:i]\n",
    "                            if next_word in mapping_dict.values():\n",
    "                                continue\n",
    "                            generate = True\n",
    "                            mapping_dict[next_pattern[0]] = next_word\n",
    "                        else:\n",
    "                            next_word = mapping_dict.get(next_pattern[0])\n",
    "                        ret = digest(next_pattern, next_word, next_string, mapping_dict)\n",
    "                        if ret is True:\n",
    "                            return True\n",
    "                        else:\n",
    "                            if next_pattern[0] in mapping_dict and generate:\n",
    "                                del mapping_dict[next_pattern[0]]\n",
    "                    return False\n",
    "\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        next_string = s\n",
    "        next_pattern = pattern\n",
    "        for i in range(1, len(next_string) + 1):\n",
    "            next_word = next_string[:i]\n",
    "            ret = digest(next_pattern, next_word, next_string, {next_pattern[0]: next_word})\n",
    "            if ret is True:\n",
    "                return True\n",
    "        if len(pattern) == len(s) == 1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        # 分别存储pattern到s以及s到pattern的***射。搞2个字典是因为2边都不能重复，方便后面判断\n",
    "        p_s_map = {}\n",
    "        s_p_map = {}\n",
    "        def is_match(pattern,s):\n",
    "            # pattern和s刚好匹配完就是成功了，只剩下一个就是失败\n",
    "            if not pattern and not s:\n",
    "                return True\n",
    "            if not pattern or not s:\n",
    "                return False\n",
    "\n",
    "            # 再细化考虑pattern和s都有剩余的情况\n",
    "            p0 = pattern[0]\n",
    "            # pattern的第一个已经在***射里，先看s的开头是不是和pattern的第一个一致。如果是，再递归判断剩余部分\n",
    "            if p0 in p_s_map:\n",
    "                except_s0 = p_s_map[p0]\n",
    "                n = len(except_s0)\n",
    "                if s[:n] != except_s0:\n",
    "                    return False\n",
    "                return is_match(pattern[1:], s[n:])\n",
    "\n",
    "            # pattern的第一个不在***射里，就从s开头一个一个挑字符尝试***射，注意跳过已经被其他pattern***射过的s\n",
    "            else:\n",
    "                for i in range(len(s)):\n",
    "                    if s[:i+1] in s_p_map:\n",
    "                        continue\n",
    "                    p_s_map[p0] = s[:i+1]\n",
    "                    s_p_map[s[:i+1]] = p0\n",
    "                    if is_match(pattern[1:], s[i+1:]):\n",
    "                        return True\n",
    "                    s_p_map.pop(s[:i+1])\n",
    "                # 尝试成功就返回True，不成功就还原***射表，返回Fasle\n",
    "                p_s_map.pop(p0,None)\n",
    "                return False\n",
    "\n",
    "        return is_match(pattern, s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        def back_tracking(patternIdx: int, sIdx: int, pattern: str, s: str, mapDict: dict) -> bool:\n",
    "            if patternIdx >= len(pattern) and sIdx < len(s):\n",
    "                return False\n",
    "            if patternIdx < len(pattern) and sIdx >= len(s):\n",
    "                return False\n",
    "            \n",
    "            if patternIdx >= len(pattern) and sIdx >= len(s):\n",
    "                return True\n",
    "            \n",
    "            char = pattern[patternIdx]\n",
    "            if char in mapDict and mapDict[char] == s[sIdx:sIdx + len(mapDict[char])]:\n",
    "                return back_tracking(patternIdx + 1, sIdx + len(mapDict[char]), pattern, s, mapDict)\n",
    "            if char not in mapDict:\n",
    "                for length in range(1, len(s) + 1):\n",
    "                    if s[sIdx:sIdx + length] in mapDict.values():\n",
    "                        continue\n",
    "                    mapDict[char] = s[sIdx:sIdx + length]\n",
    "                    if back_tracking(patternIdx + 1, sIdx + length, pattern, s, mapDict):\n",
    "                        return True\n",
    "                    else:\n",
    "                        del mapDict[char]\n",
    "                        continue\n",
    "                return False\n",
    "        return back_tracking(0, 0, pattern, s, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "\n",
    "        def is_ok(p, word, prev_map):\n",
    "            if len(p) == 1:\n",
    "                if p in prev_map:\n",
    "                    if prev_map[p] == word:\n",
    "                        return True\n",
    "                    return False\n",
    "                else:\n",
    "                    if word in prev_map.values():\n",
    "                        return False\n",
    "                    return True\n",
    "            else:\n",
    "                for i in range(1, len(word)):\n",
    "                    sub1 = word[:i]\n",
    "                    if p[0] in prev_map:\n",
    "                        if prev_map[p[0]] == sub1:\n",
    "                            ans1 = is_ok(p[1:], word[i:], prev_map)\n",
    "                            if ans1:\n",
    "                                return True\n",
    "                    else:\n",
    "                        if sub1 not in prev_map.values():\n",
    "                            pp1 = prev_map.copy()\n",
    "                            pp1[p[0]] = sub1\n",
    "                            ans1 = is_ok(p[1:], word[i:], pp1)\n",
    "                            if ans1:\n",
    "                                return True\n",
    "                return False\n",
    "\n",
    "        ret = is_ok(pattern, s, {})\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 291\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        if not pattern or not s:                #因为题目要求的对应关系都是非空的\n",
    "            return False\n",
    "        self.char_word = defaultdict(str)\n",
    "        self.word_char = defaultdict(chr)\n",
    " \n",
    "        return self.dfs_backtrace(pattern, 0, s, 0)\n",
    " \n",
    "    def dfs_backtrace(self, pattern: str, pi: int, s: str, si: int) -> bool:\n",
    "        if pi >= len(pattern):\n",
    "            return si >= len(s)\n",
    "        if si >= len(s):\n",
    "            return False\n",
    "        c = pattern[pi]\n",
    "        if c not in self.char_word:\n",
    "            for i in range(si, len(s)):\n",
    "                word = s[si: i+1]\n",
    "                if word not in self.word_char:\n",
    "                    self.char_word[c] = word        #赋值\n",
    "                    self.word_char[word] = c        #赋值\n",
    "                    \n",
    "                    if self.dfs_backtrace(pattern, pi + 1, s, i + 1) == True:\n",
    "                        return True\n",
    "                    \n",
    "                    del self.char_word[c]        #回溯。\n",
    "                    del self.word_char[word]     #回溯。\n",
    "                else:\n",
    "                    if self.word_char[word] == c:    #满足双向映射\n",
    "                        if self.dfs_backtrace(pattern, pi + 1, s, si+len(word)):\n",
    "                            return True\n",
    "        else:\n",
    "            word = self.char_word[c]\n",
    "            if si + len(word) <= len(s):\n",
    "                tmp = s[si : si+len(word)]\n",
    "                if tmp == word:\n",
    "                    if self.dfs_backtrace(pattern, pi + 1, s, si + len(word)) == True:\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "ab -> reddog\n",
    "a-> r\n",
    "b-> eddog\n",
    "也是可以的，目的是为了判断abab 这样的\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "\n",
    "        def dfs(i, j, pattern_to_word, word_to_pattern):\n",
    "            # 如果两个都使用完了，说明找到一个解\n",
    "            if i == len(pattern) and j == len(s):\n",
    "                print(pattern_to_word)\n",
    "                print(word_to_pattern)\n",
    "                return True\n",
    "            # 如果只有一个用完了，说明没有找到解\n",
    "            if i == len(pattern) or j == len(s):\n",
    "                return False\n",
    "\n",
    "            p = pattern[i]\n",
    "\n",
    "            # 我们每次从s[j] 开始不断延长找word\n",
    "            # 如果不存在这样的mapping, 我们就尝试mapping\n",
    "                # 建立映射后，进入一下层递归\n",
    "                # 如果下一层返回True, 当前的映射有效果\n",
    "                # 如果返回False, 撤回当前的映射，尝试下一个有可能的子串\n",
    "            # 如果存在这样的mapping,我们就检查映射是否一致\n",
    "                # 一致的话，进入下一层递归\n",
    "                # 不一致的话，尝试下一个可能的子串\n",
    "            for k in range(j, len(s)):\n",
    "                word = s[j: k + 1]\n",
    "\n",
    "                if p not in pattern_to_word and word not in word_to_pattern:\n",
    "                    pattern_to_word[p] = word\n",
    "                    word_to_pattern[word] = p\n",
    "\n",
    "                    if dfs(i + 1, k + 1, pattern_to_word, word_to_pattern):\n",
    "                        return True\n",
    "\n",
    "                    del pattern_to_word[p]\n",
    "                    del word_to_pattern[word]\n",
    "                elif pattern_to_word.get(p) == word and word_to_pattern.get(word) == p:\n",
    "                    if dfs(i + 1, k + 1, pattern_to_word, word_to_pattern):\n",
    "                        return True\n",
    "            \n",
    "            return False\n",
    "            \n",
    "\n",
    "        return dfs(0, 0, {}, {})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        def backtrack(i, j):\n",
    "            if i == len(pattern) and j == len(s):\n",
    "                return True\n",
    "            if i == len(pattern) or j == len(s):\n",
    "                return False\n",
    "\n",
    "            # Try to map pattern[i] to every prefix of s[j:]\n",
    "            for end in range(j + 1, len(s) + 1):\n",
    "                p, w = pattern[i], s[j:end]\n",
    "                if (p in p2w and p2w[p] == w) or (w in w2p and w2p[w] == p):\n",
    "                    if backtrack(i + 1, end):\n",
    "                        return True\n",
    "                elif p not in p2w and w not in w2p:\n",
    "                    p2w[p], w2p[w] = w, p\n",
    "                    if backtrack(i + 1, end):\n",
    "                        return True\n",
    "                    p2w.pop(p)\n",
    "                    w2p.pop(w)\n",
    "\n",
    "            return False\n",
    "\n",
    "        p2w, w2p = {}, {}\n",
    "        return backtrack(0, 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        if len(s) < len(pattern):\n",
    "            return False\n",
    "\n",
    "        char_num_dict = {}\n",
    "\n",
    "        for char_item in pattern:\n",
    "            char_num_dict[char_item] = char_num_dict.get(char_item, 0) + 1\n",
    "        \n",
    "        char_keys = list(char_num_dict)\n",
    "        \n",
    "        char_len_dict = {}\n",
    "\n",
    "        found = False\n",
    "\n",
    "        def bt(idx):\n",
    "            nonlocal found\n",
    "            if found:\n",
    "                return\n",
    "            if idx == len(char_keys):\n",
    "                total_len = 0\n",
    "                for char_item in char_keys:\n",
    "                    total_len += char_len_dict[char_item] * char_num_dict[char_item]\n",
    "                if total_len != len(s):\n",
    "                    return\n",
    "                \n",
    "                idx = 0\n",
    "                char_word_dict = {}\n",
    "                word_char_dict = {}\n",
    "                for char_item in pattern:\n",
    "                    sub_word = s[idx: idx + char_len_dict[char_item]]\n",
    "                    if char_item not in char_word_dict:\n",
    "                        char_word_dict[char_item] = sub_word\n",
    "                    elif char_word_dict[char_item] != sub_word:\n",
    "                        return\n",
    "                    \n",
    "                    if sub_word not in word_char_dict:\n",
    "                        word_char_dict[sub_word] = char_item\n",
    "                    elif char_item != word_char_dict[sub_word]:\n",
    "                        return\n",
    "                    \n",
    "                    idx += char_len_dict[char_item]\n",
    "                found = True\n",
    "                return\n",
    "            else:\n",
    "                accumulate_len = 0\n",
    "                for char_idx in range(idx):\n",
    "                    accumulate_len += char_num_dict[char_keys[char_idx]] * char_len_dict[char_keys[char_idx]]\n",
    "                if accumulate_len > len(s):\n",
    "                    return\n",
    "                remain_len = len(s) - accumulate_len\n",
    "                for valid_len in range(1, remain_len // char_num_dict[char_keys[idx]] + 1):\n",
    "                    char_len_dict[char_keys[idx]] = valid_len\n",
    "                    bt(idx + 1)\n",
    "                    char_len_dict.pop(char_keys[idx])\n",
    "        \n",
    "        bt(0)\n",
    "        return found\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        # 分别存储pattern到s以及s到pattern的***射。搞2个字典是因为2边都不能重复，方便后面判断\n",
    "        p_s_map = {}\n",
    "        s_p_map = {}\n",
    "\n",
    "\n",
    "        def is_match(pattern,s):\n",
    "            # pattern和s刚好匹配完就是成功了，只剩下一个就是失败\n",
    "            if not pattern and not s:\n",
    "                return True\n",
    "            if not pattern or not s:\n",
    "                return False\n",
    "\n",
    "            # 再细化考虑pattern和s都有剩余的情况\n",
    "            p0 = pattern[0]\n",
    "            # pattern的第一个已经在***射里，先看s的开头是不是和pattern的第一个一致。如果是，再递归判断剩余部分\n",
    "            if p0 in p_s_map:\n",
    "                except_s0 = p_s_map[p0]\n",
    "                n = len(except_s0)\n",
    "                if s[:n] != except_s0:\n",
    "                    return False\n",
    "                return is_match(pattern[1:], s[n:])\n",
    "\n",
    "            # pattern的第一个不在***射里，就从s开头一个一个挑字符尝试***射，注意跳过已经被其他pattern***射过的s\n",
    "            else:\n",
    "                for i in range(len(s)):\n",
    "                    if s[:i+1] in s_p_map:\n",
    "                        continue\n",
    "                    p_s_map[p0] = s[:i+1]\n",
    "                    s_p_map[s[:i+1]] = p0\n",
    "                    if is_match(pattern[1:], s[i+1:]):\n",
    "                        return True\n",
    "                    s_p_map.pop(s[:i+1])\n",
    "                # 尝试成功就返回True，不成功就还原***射表，返回Fasle\n",
    "                p_s_map.pop(p0,None)\n",
    "                return False\n",
    "\n",
    "        return is_match(pattern, s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        hashMap = dict()\n",
    "        return self.dfs(pattern, 0, s, 0, hashMap)\n",
    "    \n",
    "    def dfs(self, pattern, pIndex, s, sIndex, hashMap):\n",
    "        # pattern 已经匹配到最后位置\n",
    "        if pIndex == len(pattern):\n",
    "            # 检查 s 是否也全部匹配完成\n",
    "            return sIndex == len(s)\n",
    "        \n",
    "        curPattern = pattern[pIndex]\n",
    "\n",
    "        # 遇到已经匹配过的 pattern 直接检查能否满足要求\n",
    "        if curPattern in hashMap:\n",
    "            matchWord = hashMap[curPattern]\n",
    "            if s[sIndex : sIndex + len(matchWord)] != matchWord:\n",
    "                return False\n",
    "            return self.dfs(pattern, pIndex + 1, s, sIndex + len(matchWord), hashMap)\n",
    "        \n",
    "        res = False\n",
    "\n",
    "        # 如果遇到新的 pattern 需要尝试匹配新映射关系 curPattern -> newString\n",
    "        for endIndex in range(sIndex + 1, len(s) + 1):\n",
    "            possibleWord = s[sIndex : endIndex]\n",
    "            # 已有s里word对应, 但没有pattern\n",
    "            if possibleWord in hashMap.values():\n",
    "                continue\n",
    "            # 保存这种 新的对应关系\n",
    "            hashMap[curPattern] = possibleWord\n",
    "\n",
    "            res = res or self.dfs(pattern, pIndex + 1, s, sIndex + len(possibleWord), hashMap)\n",
    "            del hashMap[curPattern]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        dic = collections.defaultdict(str)\n",
    "        dic2 = collections.defaultdict(str)\n",
    "        len_p = len(pattern)\n",
    "        len_s = len(s)\n",
    "\n",
    "        def helper(id_s, id_p):\n",
    "            if id_p >= len_p or id_s >= len_s:\n",
    "                \n",
    "                if id_p == len_p and id_s == len_s:\n",
    "                    return True\n",
    "                return False\n",
    "                \n",
    "            c = pattern[id_p]\n",
    "            \n",
    "            if c in dic:\n",
    "                ss = dic[c]\n",
    "                if id_s + len(ss) > len_s:\n",
    "                    return False\n",
    "                if s[id_s: id_s+len(ss)] == ss:\n",
    "                    if helper(id_s+len(ss), id_p+1):\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                for j in range(id_s, len_s):\n",
    "                    s_curr = s[id_s: j+1]\n",
    "                    if s_curr in dic2:\n",
    "                        continue\n",
    "                    dic[c] = s_curr\n",
    "                    dic2[s_curr] = c\n",
    "                    if helper(j+1, id_p+1):\n",
    "                        return True\n",
    "                    dic.pop(c)\n",
    "                    dic2.pop(s_curr)\n",
    "                print(dict)\n",
    "            return False\n",
    "\n",
    "        \n",
    "                    \n",
    "        res = helper(0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 <= pattern.length, s.length <= 20 长度很小，可以用判断2字符串是否等这种On算法\n",
    "# from collections import defaultdict\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        print(f'输入：{pattern},{s}')\n",
    "        len_p, len_s = len(pattern), len(s)\n",
    "        print(f's长度:{len_s}')\n",
    "\n",
    "        # 所有类型确定时调用的check函数\n",
    "        def isFit():\n",
    "            # start, end = 0, 0\n",
    "            temp = ''\n",
    "            judge = set()\n",
    "            l0 = []\n",
    "            for sp in pattern:\n",
    "                # start, end = end, end+hash[sp][1]\n",
    "                m_s = hash[sp][0]\n",
    "                l0.append(m_s)\n",
    "                temp += m_s\n",
    "            judge.update(l0)  # 因为ababc中 ab映射同样的字符串会判错  \n",
    "            \n",
    "            return True if temp == s and len(judge)==len(hash)  else False\n",
    "        \n",
    "        # 1.构建先验哈希表\n",
    "        hash = {}\n",
    "        for sp in pattern:\n",
    "            if sp not in hash:\n",
    "                hash[sp] = ['', 0, 1]# 分别是：对应的字符串、对应字符串长度、pattern中该字符总个数\n",
    "            else:\n",
    "                hash[sp][2]+=1    \n",
    "        # print(hash)    \n",
    "\n",
    "        # 2.回溯搜索\n",
    "        stack = []# 装入已被映射的pattern字母\n",
    "        cur_p, cur_s = 0, 0\n",
    "        sum_rt = 0\n",
    "        while cur_p < len_p:\n",
    "            # print('\\n')\n",
    "            # print(f'当前cur_p:{cur_p}')\n",
    "            # print(f'当前hash:{hash}')\n",
    "            # print(f'当前stack:{stack}')\n",
    "            # print(f'当前sum_rt:{sum_rt}')\n",
    "            sp = pattern[cur_p]\n",
    "            # 当这是新类型\n",
    "            if hash[sp][0] == '':\n",
    "                # 如果是最后一个新类型，直接给它映射固定长度字符串\n",
    "                if len(stack) == len(hash)-1:\n",
    "                    # print(f'是最后一个新类型:{sp}')\n",
    "                    Undivisible = (len_s - sum_rt) % hash[sp][2]\n",
    "                    # print(111111111,Undivisible)\n",
    "                    # 无法被整除：即最后一个类型无法均匀分配剩余s,则回溯\n",
    "                    if Undivisible:\n",
    "                        err = stack.pop()\n",
    "                        kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                        sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # init回溯元素的匹配字符串\n",
    "                        backtracking = pattern[cur_p]\n",
    "                        hash[backtracking][0] = ''\n",
    "                        continue\n",
    "                    # 最后一个新类型能均匀分配剩余s\n",
    "                    else:\n",
    "                        print(f'{sp}：长度{(len_s - sum_rt)/hash[sp][2]}')\n",
    "                        hash[sp][1] = int((len_s - sum_rt)/hash[sp][2])# 已经能整除,int是为了？？？？\n",
    "                        h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                        # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                        hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                        print(hash)\n",
    "                        sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # 如果最后一个类型被分配长度为0的字符串，回溯（+最后一个元素总长是不会超过限度的，我就是适应总长给它分配长度的啊！）\n",
    "                        if  hash[sp][1]==0:\n",
    "                            sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                            hash[sp][1] = 0 # 初始化当前元素 \n",
    "                            hash[sp][0] = ''# 初始化当前元素 \n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        # 如果正常，则最后元素也放进stack，指针更新，等下面的check\n",
    "                        else:    \n",
    "                            stack.append([sp, cur_p, cur_s]) \n",
    "                            cur_p+=1\n",
    "                            cur_s = cur_s + h1 \n",
    "\n",
    "                # 当前是新类型，但不是最后一个新类型（这里包含2种情况：正常检查 or 回溯再检查）\n",
    "                else:\n",
    "                    # print(sp,'haaaaaaaaaaa')\n",
    "                    # print(sp,hash[sp])\n",
    "                    hash[sp][1] += 1# 可以认为是回溯过来的 \n",
    "                    # print(sp,hash[sp])\n",
    "                    h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                    # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                    hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                       \n",
    "                    sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    # 如果总长超过了限度，回溯\n",
    "                    if sum_rt > len_s:\n",
    "                        # print('超长了！！！！！！')\n",
    "                        sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                        hash[sp][1] = 0 # 初始化当前元素 \n",
    "                        hash[sp][0] = ''# 初始化当前元素 \n",
    "                        if stack:# 总长超限度case1：ababc c回溯到第一个b，即将再回溯到a\n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        else:# 总长超限度case2： aa 对应 s=abcadc 刚回溯到第一个a，stack已经pop空了\n",
    "                            return False # 第一个元素都超长了，再回溯只会给第一个元素长度+1,还是超长\n",
    "\n",
    "                    else:    \n",
    "                        stack.append([sp, cur_p, cur_s]) \n",
    "                        cur_p+=1\n",
    "                        cur_s = cur_s + h1 \n",
    "                        \n",
    "            # 当这不是新类型\n",
    "            elif hash[sp][0] != '':\n",
    "                # print(f'不是新类型，当前cur_p:{cur_p}')\n",
    "                # print(f'不是新类型，当前类型的长度:{hash[sp][1]}')\n",
    "                # print(type(cur_s))\n",
    "                h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                if hash[sp][0] == s[cur_s : cur_s + h1]:\n",
    "                    cur_p+=1\n",
    "                    cur_s += hash[sp][1]\n",
    "                    continue\n",
    "                else:\n",
    "                    # sum_rt -= hash[sp][1]*hash[sp][2]# sp是当前类型，但我们要修改的是栈顶类型！！\n",
    "                    # 例如ababc，如果第二个a不符合，我们要修改的不是a，是栈顶的b\n",
    "                    err = stack.pop()\n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    \n",
    "                    # if sp!=kind:# 如果是回溯到当前类型b 之前的类型a，就初始化b\n",
    "                    #     hash[sp][0], hash[sp][1] = '', 0\n",
    "                    \n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "                    continue\n",
    "            \n",
    "            # check\n",
    "            if len(stack)==len(hash):\n",
    "                res = isFit()\n",
    "                print(hash,res)\n",
    "                if res:\n",
    "                    return True\n",
    "                else:# 防止abba这种情况，b1作为最后一个类型会被自动分配字符串 \n",
    "                        # ifb1不行 会进入b2，然后b2如果不符，指针又会到b1，又会自动分配刚刚的字符串，进入死循环\n",
    "                    # pop的作用就是：还是进入到b2，b2发现不行后，指针会回到a1\n",
    "                    last = stack.pop()# 先把最后的类型pop掉\n",
    "                    p_last = last[0]\n",
    "                    sum_rt -= hash[p_last][1]*hash[p_last][2]# 因为此时b的长度是不对的\n",
    "                    hash[p_last][0] = ''# 初始化最后类型的hash表\n",
    "                    hash[p_last][1] = 0 # 初始化最后类型的hash表\n",
    "                    \n",
    "\n",
    "                    err = stack.pop() # 再把倒数第2类型pop出来  \n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]# 指针直接回到倒数第二类型\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# 因为此时b的长度是不对的 \n",
    "\n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "# if True:\n",
    "#     # 测试对象\n",
    "#     pattern, s = 'sucks', 'teezmnoteez'\n",
    "#     # 实例化调用\n",
    "#     a = Solution()    \n",
    "#     res = a.wordPatternMatch(pattern, s)\n",
    "#     print(f'输出:{res}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 <= pattern.length, s.length <= 20 长度很小，可以用判断2字符串是否等这种On算法\n",
    "# from collections import defaultdict\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        print(f'输入：{pattern},{s}')\n",
    "        len_p, len_s = len(pattern), len(s)\n",
    "        print(f's长度:{len_s}')\n",
    "\n",
    "        # 所有类型确定时调用的check函数\n",
    "        def isFit():\n",
    "            # start, end = 0, 0\n",
    "            temp = ''\n",
    "            judge = set()\n",
    "            l0 = []\n",
    "            for sp in pattern:\n",
    "                # start, end = end, end+hash[sp][1]\n",
    "                m_s = hash[sp][0]\n",
    "                l0.append(m_s)\n",
    "                temp += m_s\n",
    "            judge.update(l0)  # 因为ababc中 ab映射同样的字符串会判错  \n",
    "            \n",
    "            return True if temp == s and len(judge)==len(hash)  else False\n",
    "        \n",
    "        # 1.构建先验哈希表\n",
    "        hash = {}\n",
    "        for sp in pattern:\n",
    "            if sp not in hash:\n",
    "                hash[sp] = ['', 0, 1]# 分别是：对应的字符串、对应字符串长度、pattern中该字符总个数\n",
    "            else:\n",
    "                hash[sp][2]+=1    \n",
    "        # print(hash)    \n",
    "\n",
    "        # 2.回溯搜索\n",
    "        stack = []# 装入已被映射的pattern字母\n",
    "        cur_p, cur_s = 0, 0\n",
    "        sum_rt = 0\n",
    "        while cur_p < len_p:\n",
    "            # print('\\n')\n",
    "            # print(f'当前cur_p:{cur_p}')\n",
    "            # print(f'当前hash:{hash}')\n",
    "            # print(f'当前stack:{stack}')\n",
    "            # print(f'当前sum_rt:{sum_rt}')\n",
    "            sp = pattern[cur_p]\n",
    "            # 当这是新类型\n",
    "            if hash[sp][0] == '':\n",
    "                # 如果是最后一个新类型，直接给它映射固定长度字符串\n",
    "                if len(stack) == len(hash)-1:\n",
    "                    # print(f'是最后一个新类型:{sp}')\n",
    "                    Undivisible = (len_s - sum_rt) % hash[sp][2]\n",
    "                    # print(111111111,Undivisible)\n",
    "                    # 无法被整除：即最后一个类型无法均匀分配剩余s,则回溯\n",
    "                    if Undivisible:\n",
    "                        err = stack.pop()\n",
    "                        kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                        sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # init回溯元素的匹配字符串\n",
    "                        backtracking = pattern[cur_p]\n",
    "                        hash[backtracking][0] = ''\n",
    "                        continue\n",
    "                    # 最后一个新类型能均匀分配剩余s\n",
    "                    else:\n",
    "                        print(f'{sp}：长度{(len_s - sum_rt)/hash[sp][2]}')\n",
    "                        hash[sp][1] = int((len_s - sum_rt)/hash[sp][2])# 已经能整除,int是为了？？？？\n",
    "                        h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                        # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                        hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                        print(hash)\n",
    "                        sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # 如果最后一个类型被分配长度为0的字符串，回溯（+最后一个元素总长是不会超过限度的，我就是适应总长给它分配长度的啊！）\n",
    "                        if  hash[sp][1]==0:\n",
    "                            sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                            hash[sp][1] = 0 # 初始化当前元素 \n",
    "                            hash[sp][0] = ''# 初始化当前元素 \n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        # 如果正常，则最后元素也放进stack，指针更新，等下面的check\n",
    "                        else:    \n",
    "                            stack.append([sp, cur_p, cur_s]) \n",
    "                            cur_p+=1\n",
    "                            cur_s = cur_s + h1 \n",
    "\n",
    "                # 当前是新类型，但不是最后一个新类型（这里包含2种情况：正常检查 or 回溯再检查）\n",
    "                else:\n",
    "                    # print(sp,'haaaaaaaaaaa')\n",
    "                    # print(sp,hash[sp])\n",
    "                    hash[sp][1] += 1# 可以认为是回溯过来的 \n",
    "                    # print(sp,hash[sp])\n",
    "                    h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                    # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                    hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                       \n",
    "                    sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    # 如果总长超过了限度，回溯\n",
    "                    if sum_rt > len_s:\n",
    "                        # print('超长了！！！！！！')\n",
    "                        sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                        hash[sp][1] = 0 # 初始化当前元素 \n",
    "                        hash[sp][0] = ''# 初始化当前元素 \n",
    "                        if stack:# 总长超限度case1：ababc c回溯到第一个b，即将再回溯到a\n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        else:# 总长超限度case2： aa 对应 s=abcadc 刚回溯到第一个a，stack已经pop空了\n",
    "                            return False # 第一个元素都超长了，再回溯只会给第一个元素长度+1,还是超长\n",
    "\n",
    "                    else:    \n",
    "                        stack.append([sp, cur_p, cur_s]) \n",
    "                        cur_p+=1\n",
    "                        cur_s = cur_s + h1 \n",
    "                        \n",
    "            # 当这不是新类型\n",
    "            elif hash[sp][0] != '':\n",
    "                # print(f'不是新类型，当前cur_p:{cur_p}')\n",
    "                # print(f'不是新类型，当前类型的长度:{hash[sp][1]}')\n",
    "                # print(type(cur_s))\n",
    "                h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                if hash[sp][0] == s[cur_s : cur_s + h1]:\n",
    "                    cur_p+=1\n",
    "                    cur_s += hash[sp][1]\n",
    "                    continue\n",
    "                else:\n",
    "                    # sum_rt -= hash[sp][1]*hash[sp][2]# sp是当前类型，但我们要修改的是栈顶类型！！\n",
    "                    # 例如ababc，如果第二个a不符合，我们要修改的不是a，是栈顶的b\n",
    "                    err = stack.pop()\n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    \n",
    "                    # if sp!=kind:# 如果是回溯到当前类型b 之前的类型a，就初始化b\n",
    "                    #     hash[sp][0], hash[sp][1] = '', 0\n",
    "                    \n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "                    continue\n",
    "            \n",
    "            # check\n",
    "            if len(stack)==len(hash):\n",
    "                res = isFit()\n",
    "                print(hash,res)\n",
    "                if res:\n",
    "                    return True\n",
    "                else:# 防止abba这种情况，b1作为最后一个类型会被自动分配字符串 \n",
    "                        # ifb1不行 会进入b2，然后b2如果不符，指针又会到b1，又会自动分配刚刚的字符串，进入死循环\n",
    "                    # pop的作用就是：还是进入到b2，b2发现不行后，指针会回到a1\n",
    "                    last = stack.pop()# 先把最后的类型pop掉\n",
    "                    p_last = last[0]\n",
    "                    sum_rt -= hash[p_last][1]*hash[p_last][2]# 因为此时b的长度是不对的\n",
    "                    hash[p_last][0] = ''# 初始化最后类型的hash表\n",
    "                    hash[p_last][1] = 0 # 初始化最后类型的hash表\n",
    "                    \n",
    "\n",
    "                    err = stack.pop() # 再把倒数第2类型pop出来  \n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]# 指针直接回到倒数第二类型\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# 因为此时b的长度是不对的 \n",
    "\n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "# if True:\n",
    "#     # 测试对象\n",
    "#     pattern, s = 'sucks', 'teezmnoteez'\n",
    "#     # 实例化调用\n",
    "#     a = Solution()    \n",
    "#     res = a.wordPatternMatch(pattern, s)\n",
    "#     print(f'输出:{res}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 <= pattern.length, s.length <= 20 长度很小，可以用判断2字符串是否等这种On算法\n",
    "# from collections import defaultdict\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        print(f'输入：{pattern},{s}')\n",
    "        len_p, len_s = len(pattern), len(s)\n",
    "        print(f's长度:{len_s}')\n",
    "\n",
    "        # 所有类型确定时调用的check函数\n",
    "        def isFit():\n",
    "            # start, end = 0, 0\n",
    "            temp = ''\n",
    "            judge = set()\n",
    "            l0 = []\n",
    "            for sp in pattern:\n",
    "                # start, end = end, end+hash[sp][1]\n",
    "                m_s = hash[sp][0]\n",
    "                l0.append(m_s)\n",
    "                temp += m_s\n",
    "            judge.update(l0)  # 因为ababc中 ab映射同样的字符串会判错  \n",
    "            \n",
    "            return True if temp == s and len(judge)==len(hash)  else False\n",
    "        \n",
    "        # 1.构建先验哈希表\n",
    "        hash = {}\n",
    "        for sp in pattern:\n",
    "            if sp not in hash:\n",
    "                hash[sp] = ['', 0, 1]# 分别是：对应的字符串、对应字符串长度、pattern中该字符总个数\n",
    "            else:\n",
    "                hash[sp][2]+=1    \n",
    "        # print(hash)    \n",
    "\n",
    "        # 2.回溯搜索\n",
    "        stack = []# 装入已被映射的pattern字母\n",
    "        cur_p, cur_s = 0, 0\n",
    "        sum_rt = 0\n",
    "        while cur_p < len_p:\n",
    "            # print('\\n')\n",
    "            # print(f'当前cur_p:{cur_p}')\n",
    "            # print(f'当前hash:{hash}')\n",
    "            # print(f'当前stack:{stack}')\n",
    "            # print(f'当前sum_rt:{sum_rt}')\n",
    "            sp = pattern[cur_p]\n",
    "            # 当这是新类型\n",
    "            if hash[sp][0] == '':\n",
    "                # 如果是最后一个新类型，直接给它映射固定长度字符串\n",
    "                if len(stack) == len(hash)-1:\n",
    "                    # print(f'是最后一个新类型:{sp}')\n",
    "                    Undivisible = (len_s - sum_rt) % hash[sp][2]\n",
    "                    # print(111111111,Undivisible)\n",
    "                    # 无法被整除：即最后一个类型无法均匀分配剩余s,则回溯\n",
    "                    if Undivisible:\n",
    "                        err = stack.pop()\n",
    "                        kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                        sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # init回溯元素的匹配字符串\n",
    "                        backtracking = pattern[cur_p]\n",
    "                        hash[backtracking][0] = ''\n",
    "                        continue\n",
    "                    # 最后一个新类型能均匀分配剩余s\n",
    "                    else:\n",
    "                        print(f'{sp}：长度{(len_s - sum_rt)/hash[sp][2]}')\n",
    "                        hash[sp][1] = int((len_s - sum_rt)/hash[sp][2])# 已经能整除,int是为了？？？？\n",
    "                        h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                        # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                        hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                        print(hash)\n",
    "                        sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # 如果最后一个类型被分配长度为0的字符串，回溯（+最后一个元素总长是不会超过限度的，我就是适应总长给它分配长度的啊！）\n",
    "                        if  hash[sp][1]==0:\n",
    "                            sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                            hash[sp][1] = 0 # 初始化当前元素 \n",
    "                            hash[sp][0] = ''# 初始化当前元素 \n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        # 如果正常，则最后元素也放进stack，指针更新，等下面的check\n",
    "                        else:    \n",
    "                            stack.append([sp, cur_p, cur_s]) \n",
    "                            cur_p+=1\n",
    "                            cur_s = cur_s + h1 \n",
    "\n",
    "                # 当前是新类型，但不是最后一个新类型（这里包含2种情况：正常检查 or 回溯再检查）\n",
    "                else:\n",
    "                    # print(sp,'haaaaaaaaaaa')\n",
    "                    # print(sp,hash[sp])\n",
    "                    hash[sp][1] += 1# 可以认为是回溯过来的 \n",
    "                    # print(sp,hash[sp])\n",
    "                    h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                    # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                    hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                       \n",
    "                    sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    # 如果总长超过了限度，回溯\n",
    "                    if sum_rt > len_s:\n",
    "                        # print('超长了！！！！！！')\n",
    "                        sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                        hash[sp][1] = 0 # 初始化当前元素 \n",
    "                        hash[sp][0] = ''# 初始化当前元素 \n",
    "                        if stack:# 总长超限度case1：ababc c回溯到第一个b，即将再回溯到a\n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        else:# 总长超限度case2： aa 对应 s=abcadc 刚回溯到第一个a，stack已经pop空了\n",
    "                            return False # 第一个元素都超长了，再回溯只会给第一个元素长度+1,还是超长\n",
    "\n",
    "                    else:    \n",
    "                        stack.append([sp, cur_p, cur_s]) \n",
    "                        cur_p+=1\n",
    "                        cur_s = cur_s + h1 \n",
    "                        \n",
    "            # 当这不是新类型\n",
    "            elif hash[sp][0] != '':\n",
    "                # print(f'不是新类型，当前cur_p:{cur_p}')\n",
    "                # print(f'不是新类型，当前类型的长度:{hash[sp][1]}')\n",
    "                # print(type(cur_s))\n",
    "                h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                if hash[sp][0] == s[cur_s : cur_s + h1]:\n",
    "                    cur_p+=1\n",
    "                    cur_s += hash[sp][1]\n",
    "                    continue\n",
    "                else:\n",
    "                    # sum_rt -= hash[sp][1]*hash[sp][2]# sp是当前类型，但我们要修改的是栈顶类型！！\n",
    "                    # 例如ababc，如果第二个a不符合，我们要修改的不是a，是栈顶的b\n",
    "                    err = stack.pop()\n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    \n",
    "                    if sp!=kind:# 如果是回溯到当前类型b 之前的类型a，就初始化b\n",
    "                        hash[sp][0], hash[sp][1] = '', 0\n",
    "                    \n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "                    continue\n",
    "            \n",
    "            # check\n",
    "            if len(stack)==len(hash):\n",
    "                res = isFit()\n",
    "                print(hash,res)\n",
    "                if res:\n",
    "                    return True\n",
    "                else:# 防止abba这种情况，b1作为最后一个类型会被自动分配字符串 \n",
    "                        # ifb1不行 会进入b2，然后b2如果不符，指针又会到b1，又会自动分配刚刚的字符串，进入死循环\n",
    "                    # pop的作用就是：还是进入到b2，b2发现不行后，指针会回到a1\n",
    "                    last = stack.pop()# 先把最后的类型pop掉\n",
    "                    p_last = last[0]\n",
    "                    sum_rt -= hash[p_last][1]*hash[p_last][2]# 因为此时b的长度是不对的\n",
    "                    hash[p_last][0] = ''# 初始化最后类型的hash表\n",
    "                    hash[p_last][1] = 0 # 初始化最后类型的hash表\n",
    "                    \n",
    "\n",
    "                    err = stack.pop() # 再把倒数第2类型pop出来  \n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]# 指针直接回到倒数第二类型\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# 因为此时b的长度是不对的 \n",
    "\n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "# if True:\n",
    "#     # 测试对象\n",
    "#     pattern, s = 'sucks', 'teezmnoteez'\n",
    "#     # 实例化调用\n",
    "#     a = Solution()    \n",
    "#     res = a.wordPatternMatch(pattern, s)\n",
    "#     print(f'输出:{res}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 1 <= pattern.length, s.length <= 20 长度很小，可以用判断2字符串是否等这种On算法\n",
    "# from collections import defaultdict\n",
    "class Solution:\n",
    "    def wordPatternMatch(self, pattern: str, s: str) -> bool:\n",
    "        print(f'输入：{pattern},{s}')\n",
    "        len_p, len_s = len(pattern), len(s)\n",
    "        print(f's长度:{len_s}')\n",
    "\n",
    "        # 所有类型确定时调用的check函数\n",
    "        def isFit():\n",
    "            # start, end = 0, 0\n",
    "            temp = ''\n",
    "            judge = set()\n",
    "            l0 = []\n",
    "            for sp in pattern:\n",
    "                # start, end = end, end+hash[sp][1]\n",
    "                m_s = hash[sp][0]\n",
    "                l0.append(m_s)\n",
    "                temp += m_s\n",
    "            judge.update(l0)  # 因为ababc中 ab映射同样的字符串会判错  \n",
    "            \n",
    "            return True if temp == s and len(judge)==len(hash)  else False\n",
    "        \n",
    "        # 1.构建先验哈希表\n",
    "        hash = {}\n",
    "        for sp in pattern:\n",
    "            if sp not in hash:\n",
    "                hash[sp] = ['', 0, 1]# 分别是：对应的字符串、对应字符串长度、pattern中该字符总个数\n",
    "            else:\n",
    "                hash[sp][2]+=1    \n",
    "        # print(hash)    \n",
    "\n",
    "        # 2.回溯搜索\n",
    "        stack = []# 装入已被映射的pattern字母\n",
    "        cur_p, cur_s = 0, 0\n",
    "        sum_rt = 0\n",
    "        while cur_p < len_p:\n",
    "            print('\\n')\n",
    "            print(f'当前cur_p:{cur_p}')\n",
    "            print(f'当前hash:{hash}')\n",
    "            print(f'当前stack:{stack}')\n",
    "            print(f'当前sum_rt:{sum_rt}')\n",
    "            sp = pattern[cur_p]\n",
    "            # 当这是新类型\n",
    "            if hash[sp][0] == '':\n",
    "                # 如果是最后一个新类型，直接给它映射固定长度字符串\n",
    "                if len(stack) == len(hash)-1:\n",
    "                    print(f'是最后一个新类型:{sp}')\n",
    "                    Undivisible = (len_s - sum_rt) % hash[sp][2]\n",
    "                    # print(111111111,Undivisible)\n",
    "                    # 无法被整除：即最后一个类型无法均匀分配剩余s,则回溯\n",
    "                    if Undivisible:\n",
    "                        err = stack.pop()\n",
    "                        kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                        sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # init回溯元素的匹配字符串\n",
    "                        backtracking = pattern[cur_p]\n",
    "                        hash[backtracking][0] = ''\n",
    "                        continue\n",
    "                    # 最后一个新类型能均匀分配剩余s\n",
    "                    else:\n",
    "                        print(f'{sp}：长度{(len_s - sum_rt)/hash[sp][2]}')\n",
    "                        hash[sp][1] = int((len_s - sum_rt)/hash[sp][2])# 已经能整除,int是为了？？？？\n",
    "                        h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                        # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                        hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                        print(hash)\n",
    "                        sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "\n",
    "                        # 如果最后一个类型被分配长度为0的字符串，回溯（+最后一个元素总长是不会超过限度的，我就是适应总长给它分配长度的啊！）\n",
    "                        if  hash[sp][1]==0:\n",
    "                            sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                            hash[sp][1] = 0 # 初始化当前元素 \n",
    "                            hash[sp][0] = ''# 初始化当前元素 \n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        # 如果正常，则最后元素也放进stack，指针更新，等下面的check\n",
    "                        else:    \n",
    "                            stack.append([sp, cur_p, cur_s]) \n",
    "                            cur_p+=1\n",
    "                            cur_s = cur_s + h1 \n",
    "\n",
    "                # 当前是新类型，但不是最后一个新类型（这里包含2种情况：正常检查 or 回溯再检查）\n",
    "                else:\n",
    "                    # print(sp,'haaaaaaaaaaa')\n",
    "                    # print(sp,hash[sp])\n",
    "                    hash[sp][1] += 1# 可以认为是回溯过来的 \n",
    "                    # print(sp,hash[sp])\n",
    "                    h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                    # print(type(cur_s),hash[sp][1],type(hash[sp][1]))\n",
    "                    hash[sp][0] = s[cur_s : cur_s + h1]\n",
    "                       \n",
    "                    sum_rt += hash[sp][1]*hash[sp][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    # 如果总长超过了限度，回溯\n",
    "                    if sum_rt > len_s:\n",
    "                        print('超长了！！！！！！')\n",
    "                        sum_rt -= hash[sp][1]*hash[sp][2]# 减去当前元素的时间\n",
    "                        hash[sp][1] = 0 # 初始化当前元素 \n",
    "                        hash[sp][0] = ''# 初始化当前元素 \n",
    "                        if stack:# 总长超限度case1：ababc c回溯到第一个b，即将再回溯到a\n",
    "                            err = stack.pop()\n",
    "                            kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                            sum_rt -= hash[kind][1]*hash[kind][2]# 再减掉被pop元素的时间 \n",
    "\n",
    "                            # init回溯元素的匹配字符串\n",
    "                            backtracking = pattern[cur_p]\n",
    "                            hash[backtracking][0] = ''\n",
    "                            continue\n",
    "                        else:# 总长超限度case2： aa 对应 s=abcadc 刚回溯到第一个a，stack已经pop空了\n",
    "                            return False # 第一个元素都超长了，再回溯只会给第一个元素长度+1,还是超长\n",
    "\n",
    "                    else:    \n",
    "                        stack.append([sp, cur_p, cur_s]) \n",
    "                        cur_p+=1\n",
    "                        cur_s = cur_s + h1 \n",
    "                        \n",
    "            # 当这不是新类型\n",
    "            elif hash[sp][0] != '':\n",
    "                print(f'不是新类型，当前cur_p:{cur_p}')\n",
    "                print(f'不是新类型，当前类型的长度:{hash[sp][1]}')\n",
    "                print(type(cur_s))\n",
    "                h1 = int(hash[sp][1])# hash[sp][1]是float类型，不能当index\n",
    "                if hash[sp][0] == s[cur_s : cur_s + h1]:\n",
    "                    cur_p+=1\n",
    "                    cur_s += hash[sp][1]\n",
    "                    continue\n",
    "                else:\n",
    "                    # sum_rt -= hash[sp][1]*hash[sp][2]# sp是当前类型，但我们要修改的是栈顶类型！！\n",
    "                    # 例如ababc，如果第二个a不符合，我们要修改的不是a，是栈顶的b\n",
    "                    err = stack.pop()\n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# sum_rt只在类型入栈或出栈时加减\n",
    "                    \n",
    "                    if sp!=kind:# 如果是回溯到当前类型b 之前的类型a，就初始化b\n",
    "                        hash[sp][0], hash[sp][1] = '', 0\n",
    "                    \n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "                    continue\n",
    "            \n",
    "            # check\n",
    "            if len(stack)==len(hash):\n",
    "                res = isFit()\n",
    "                print(hash,res)\n",
    "                if res:\n",
    "                    return True\n",
    "                else:# 防止abba这种情况，b1作为最后一个类型会被自动分配字符串 \n",
    "                        # ifb1不行 会进入b2，然后b2如果不符，指针又会到b1，又会自动分配刚刚的字符串，进入死循环\n",
    "                    # pop的作用就是：还是进入到b2，b2发现不行后，指针会回到a1\n",
    "                    last = stack.pop()# 先把最后的类型pop掉\n",
    "                    p_last = last[0]\n",
    "                    sum_rt -= hash[p_last][1]*hash[p_last][2]# 因为此时b的长度是不对的\n",
    "                    hash[p_last][0] = ''# 初始化最后类型的hash表\n",
    "                    hash[p_last][1] = 0 # 初始化最后类型的hash表\n",
    "                    \n",
    "\n",
    "                    err = stack.pop() # 再把倒数第2类型pop出来  \n",
    "                    kind, cur_p, cur_s = err[0], err[1], err[2]# 指针直接回到倒数第二类型\n",
    "                    sum_rt -= hash[kind][1]*hash[kind][2]# 因为此时b的长度是不对的 \n",
    "\n",
    "                    # init回溯元素的匹配字符串\n",
    "                    backtracking = pattern[cur_p]\n",
    "                    hash[backtracking][0] = ''\n",
    "\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "# if True:\n",
    "#     # 测试对象\n",
    "#     pattern, s = 'sucks', 'teezmnoteez'\n",
    "#     # 实例化调用\n",
    "#     a = Solution()    \n",
    "#     res = a.wordPatternMatch(pattern, s)\n",
    "#     print(f'输出:{res}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        words = s.split()\n",
    "        if len(words) != len(pattern):\n",
    "            return False\n",
    "        if len(set(words)) != len(set(pattern)):\n",
    "            return False\n",
    "        w_to_p = {}\n",
    "        for i in range(len(words)):\n",
    "            if words[i] not in w_to_p:\n",
    "                w_to_p[words[i]] = pattern[i]\n",
    "            elif w_to_p[words[i]] != pattern[i]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern, str):\n",
    "        \"\"\"\n",
    "        :type pattern: str\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n = str.split()\n",
    "        return len(set(zip(pattern,n))) == len(set(pattern)) == len(set(n)) if len(n) == len(pattern) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern, str):\n",
    "        \"\"\"\n",
    "        :type pattern: str\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        d1, d2 = {}, {}\n",
    "        words = str.split(' ')\n",
    "        if len(words) != len(pattern):\n",
    "            return False\n",
    "        for i in range(len(words)):\n",
    "            c, w = pattern[i], words[i]\n",
    "            if c in d1:\n",
    "                if d1[c] != w:\n",
    "                    return False\n",
    "            else:\n",
    "                d1[c] = w\n",
    "            if w in d2:\n",
    "                if d2[w] != c:\n",
    "                    return False\n",
    "            else:\n",
    "                d2[w] = c\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern, str):\n",
    "        \"\"\"\n",
    "        :type pattern: str\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        word_list = str.split()\n",
    "        if len(word_list) != len(pattern):\n",
    "        \treturn False\n",
    "        return len(set(word_list)) == len(set(pattern)) == len(set(zip(word_list, pattern)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: 'str', str: 'str') -> 'bool':\n",
    "        strToList = str.split(\" \")\n",
    "        \n",
    "        if len(pattern) != len(strToList) or len(set(pattern)) != len(set(strToList)):\n",
    "            return False\n",
    "        if len(set(zip(strToList, pattern))) == len(set(pattern)):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern, str):\n",
    "        \"\"\"\n",
    "        :type pattern: str\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        t = str.split()\n",
    "        l = len(pattern)\n",
    "        if l!=len(t):\n",
    "            return False\n",
    "        map = {}\n",
    "        \n",
    "        for i in range(l):\n",
    "            if pattern[i] in map:\n",
    "                if map[pattern[i]]!=t[i]:\n",
    "                    return False\n",
    "            elif t[i] in map.values():\n",
    "                return False\n",
    "            else:\n",
    "                map[pattern[i]] = t[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        dic_pat,dic_s = {},{}\n",
    "        n,p = 1,1\n",
    "        list_pat, list_s = [], []\n",
    "        for each in pattern:\n",
    "            if each not in dic_pat:\n",
    "                dic_pat[each] = n\n",
    "                list_pat.append(dic_pat[each])\n",
    "                n += 1\n",
    "            else:\n",
    "                list_pat.append(dic_pat[each])\n",
    "        \n",
    "        l = s.split(' ')\n",
    "        for each in l:\n",
    "            if each not in dic_s:\n",
    "                dic_s[each] = p\n",
    "                list_s.append(dic_s[each])\n",
    "                p += 1\n",
    "            else:\n",
    "                list_s.append(dic_s[each])\n",
    "        \n",
    "        return list_pat == list_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, str: str) -> bool:\n",
    "        if not pattern and not str:\n",
    "            return True\n",
    "        str1 = str.split( )\n",
    "        d_pattern = {}\n",
    "        d_str = {}\n",
    "        n = 1\n",
    "        for x in pattern:\n",
    "            if x in d_pattern:\n",
    "                continue\n",
    "            else:\n",
    "                d_pattern[x] = n\n",
    "                n += 1\n",
    "        n = 1\n",
    "        for x in str1:\n",
    "            if x in d_str:\n",
    "                continue\n",
    "            else:\n",
    "                d_str[x] = n\n",
    "                n += 1\n",
    "        pattern2 = [d_pattern[x] for x in pattern]\n",
    "        str2 = [d_str[x] for x in str1]\n",
    "        return pattern2==str2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, str: str) -> bool:\n",
    "        strs = str.split()\n",
    "        if len(pattern)!=len(strs):\n",
    "            return False\n",
    "        dic = {}\n",
    "        for i in range(len(pattern)):\n",
    "            if pattern[i] in dic:\n",
    "                if dic[pattern[i]]!=strs[i]:\n",
    "                    return False\n",
    "            else:\n",
    "                dic[pattern[i]]=strs[i]\n",
    "                if i > 0:\n",
    "                    for j in range(i):\n",
    "                        if dic[pattern[i]]==dic[pattern[j]]:\n",
    "                            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, str: str) -> bool:\n",
    "\n",
    "        vec = str.split(' ')\n",
    "\n",
    "        if len(vec) != len(pattern):\n",
    "            return False\n",
    "        \n",
    "        for i in range(len(pattern)):\n",
    "            if pattern.index(pattern[i]) != vec.index(vec[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        s = s.split()\n",
    "        \n",
    "        st_1 = []\n",
    "        st_2 = []\n",
    "        s = list(s)\n",
    "        for num in s: \n",
    "            st_1.append(s.index(num))\n",
    "        for num in pattern: \n",
    "            st_2.append(pattern.index(num))\n",
    "        \n",
    "        return st_1 == st_2\n",
    "\n",
    "             \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        # ref = s.split(\" \")\n",
    "        # if len(pattern) != len(ref):\n",
    "        #     return False\n",
    "        # adict = dict()\n",
    "        # adict2 = dict()\n",
    "        # aset = set()\n",
    "        # n = len(pattern)\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     if pattern[i] not in aset:\n",
    "        #         adict[pattern[i]] = ref[i]\n",
    "        #         aset.add(pattern[i])\n",
    "        #         adict2[ref[i]] = True\n",
    "        #     else:\n",
    "        #         if ref[i] in adict2:\n",
    "        #             return False\n",
    "        #         if ref[i] != adict[pattern[i]]:\n",
    "        #             return False\n",
    "                \n",
    "        # return True\n",
    "\n",
    "\n",
    "\n",
    "        words = s.split(\" \")\n",
    "        if len(words) != len(pattern):\n",
    "            return False\n",
    "        hashMap = {}\n",
    "        mapVal = {}\n",
    "        for i in range(len(pattern)):\n",
    "            if pattern[i] in hashMap:\n",
    "                # 如果pattern[i]存在于hashMap中了，判断pattern[i] 和 word[i]是否存在对应关系\n",
    "                if hashMap[pattern[i]] != words[i]:\n",
    "                    return False\n",
    "            else:\n",
    "                # 如果pattern[i]没有在hashMap中，但word[i]之前已经出现过了，则直接返回False\n",
    "                if words[i] in mapVal:\n",
    "                    return False\n",
    "                # 建立对应关系，同时将word[i]添加到mapVal中\n",
    "                hashMap[pattern[i]] = words[i]\n",
    "                mapVal[words[i]] = True\n",
    "        return True\n",
    "\n",
    "# 作者：changyili\n",
    "# 链接：https://leetcode-cn.com/problems/word-pattern/solution/si-lu-qing-xi-dai-zhu-shi-gua-he-xin-shou-guan-kan/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        res = s.split()\n",
    "        return list(map(pattern.index, pattern)) == list(map(res.index, res))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        s = s.split()\n",
    "        if len(s) != len(pattern): return False\n",
    "\n",
    "        def recur(pattern, s):\n",
    "            h = {}\n",
    "            for i in range(len(pattern)):\n",
    "                if pattern[i] not in h: h[pattern[i]] = s[i]\n",
    "                else:\n",
    "                    word = h[pattern[i]]\n",
    "                    if word != s[i]: return False\n",
    "            return True\n",
    "\n",
    "        return recur(pattern, s) and recur(s, pattern)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        word = s.split(\" \")\n",
    "\n",
    "        if len(word) != len(pattern):\n",
    "            return False\n",
    "        \n",
    "        hashmap = {}\n",
    "        mapval = {}\n",
    "        for i in range(len(pattern)):\n",
    "            if pattern[i] in hashmap:\n",
    "                if hashmap[pattern[i]] != word[i]:\n",
    "                    return False\n",
    "            else:\n",
    "                if word[i] in mapval:\n",
    "                    return False\n",
    "                hashmap[pattern[i]] = word[i]\n",
    "                mapval[word[i]] = True\n",
    "        return True\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        words = s.split()\n",
    "        dic1 = {}\n",
    "        dic2 = {}\n",
    "        if len(pattern) != len(words):\n",
    "            return False\n",
    "        for ch, word in zip(pattern, words):\n",
    "            if (word in dic1 and dic1[word] != ch) or (ch in dic2 and dic2[ch] != word):\n",
    "                return False\n",
    "            dic1[word] = ch\n",
    "            dic2[ch] = word\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        s_list = s.split(\" \")\n",
    "        if len(pattern) != len(s_list):\n",
    "            return False\n",
    "        hash_map_p2s = dict()\n",
    "        hash_map_s2p = dict()\n",
    "        \n",
    "        for p, ch in zip(pattern, s_list):\n",
    "            if ch in hash_map_s2p:\n",
    "                if hash_map_s2p[ch] != p:\n",
    "                    return False\n",
    "            else:\n",
    "                hash_map_s2p[ch] = p\n",
    "            \n",
    "            if p in hash_map_p2s:\n",
    "                if hash_map_p2s[p] != ch:\n",
    "                    return False\n",
    "            else:\n",
    "                hash_map_p2s[p] = ch\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "\n",
    "        s_split = s.split()\n",
    "        if len(pattern)!=len(s_split):\n",
    "            return False\n",
    "        dict_p = {}\n",
    "        dict_s = {}\n",
    "        for kk in range(len(pattern)):\n",
    "            key = pattern[kk]\n",
    "            if key not in dict_p:\n",
    "                dict_p[key] = s_split[kk]\n",
    "            else:\n",
    "                if dict_p[key] != s_split[kk]:\n",
    "                    return False\n",
    "\n",
    "            key_s = s_split[kk]\n",
    "            if key_s not in dict_s:\n",
    "                dict_s[key_s] = key\n",
    "            else:\n",
    "                if dict_s[key_s] != key:\n",
    "                    return False\n",
    "\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        s = s.split()\n",
    "        if len(pattern)!=len(s): return False\n",
    "        ch_to_word = {}\n",
    "        word_to_ch = {}\n",
    "\n",
    "        n = len(pattern)\n",
    "\n",
    "        for i in range(n):\n",
    "            print(ch_to_word, word_to_ch)\n",
    "\n",
    "            if pattern[i] in ch_to_word and ch_to_word[pattern[i]] != s[i]:\n",
    "                return False\n",
    "            if s[i] in word_to_ch and word_to_ch[s[i]] != pattern[i]:\n",
    "                return False\n",
    "\n",
    "            ch_to_word[pattern[i]] = s[i]\n",
    "            word_to_ch[s[i]] = pattern[i]\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        s_list = list(s.split(\" \"))\n",
    "        \n",
    "        l_pattern = len(pattern)\n",
    "        l_sl = len(s_list)\n",
    "\n",
    "        \"\"\"如果长度不等则必然不匹配\"\"\"\n",
    "        if l_sl != l_pattern:return False\n",
    "\n",
    "        dp_pa = [[False] * l_pattern for _ in range(l_pattern)]\n",
    "        dp_sl = [[False] * l_sl for _ in range(l_sl)]\n",
    "\n",
    "        \"\"\"如果规律相同则二维矩阵将会完全一致\"\"\"\n",
    "        for i in range(l_pattern-1):\n",
    "            for j in range(i+1, l_pattern):\n",
    "                if pattern[i] == pattern[j]:dp_pa[i][j] = True\n",
    "                if s_list[i] == s_list[j]:dp_sl[i][j] = True\n",
    "        if dp_pa == dp_sl:return True\n",
    "        else:return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        d1,d2={},{}\n",
    "        words=s.split()\n",
    "        pattern_list=list(pattern)\n",
    "        if len(words)!=len(pattern_list):\n",
    "            return False\n",
    "        for c1,c2 in zip(words,pattern_list):\n",
    "            if c1 in d1 and d1[c1]!=c2:\n",
    "               return False\n",
    "            else:\n",
    "                d1[c1]=c2\n",
    "            if c2 in d2 and d2[c2]!=c1:\n",
    "                return False\n",
    "            else:\n",
    "                d2[c2]=c1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        ss = s.split()\n",
    "        p2s = {}\n",
    "        if len(pattern) != len(ss): return False\n",
    "        for a, b in zip(pattern, ss):\n",
    "            if a in p2s and p2s[a] != b: return False\n",
    "            if a not in p2s and b in p2s.values(): return False\n",
    "            p2s[a] = b\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wordPattern(self, pattern: str, s: str) -> bool:\n",
    "        ss = s.split()\n",
    "        m, n = len(pattern), len(ss)\n",
    "        if m != n: \n",
    "            return False\n",
    "\n",
    "        dic = {}\n",
    "        for i in range(m):\n",
    "            if pattern[i] in dic.keys():\n",
    "                if dic[pattern[i]] != ss[i]:\n",
    "                    return False\n",
    "                else:\n",
    "                    continue\n",
    "            else:\n",
    "                if ss[i] in dic.values():\n",
    "                    return False\n",
    "                dic[pattern[i]] = ss[i]\n",
    "        return True\n",
    "            \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
